/**
 * @param {string} text1
 * @param {string} text2
 * @return {number}
 * dp(m,n)表示：S1[0...m] 和 S2[0...n] 的最长公共子序列的长度
 * S1[m] == S[n]：dp(m,n) = 1 + dp(m - 1,n - 1)
 * dp(m,n) = max(dp(m - 1,n), dp(m,n - 1))
 */
var longestCommonSubsequence = function (text1, text2) {
  const m = text1.length;
  const n = text2.length;
  let dp = [];
  for (let i = 0; i <= m; i++) {
    dp[i] = [];
    for (let j = 0; j <= n; j++) {
      dp[i][j] = 0;
    }
  }
  for (let i = 0; i <= m; i++) {
    for (let j = 0; j <= n; j++) {
      if (i == 0 || j == 0) {
        dp[i][j] = 0;
      } else if (text1[i - 1] == text2[j - 1]) {
        dp[i][j] = dp[i - 1][j - 1] + 1;
      } else {
        dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
      }
    }
  }
  return dp[m][n];
};
